Traditional 3D rendering systems use a mesh of polygons (usually triangles) to model the objects within a scene. Triangles have the advantage that they are of a simple form, and it is therefore relatively easy to perform operations such as transformation, lighting, texturing and rasterization on them in order to produce an image for display.
A known alternative to modelling objects using a mesh of polygons is to segment the object into areas and fit a number of curved, high order surfaces, frequently termed patches, to the different areas of the object being modelled. These patches are generally defined as parametric surfaces with the surface shape governed by a grid of control points. An advantage of using high order surfaces is that the set of control points usually requires a much smaller amount of data to represent a particular model than the equivalent polygon mesh. High order surfaces are also generally easier to manipulate when animating an object which is changing in shape. A major disadvantage of modelling using high order surfaces is that it introduces added complexity in the rasterization stage of the rendering system.
It is also known to use high order surfaces for the modelling stage and to convert the surfaces to a series of tessellating triangles before performing processing stages such as rasterization. This combined method benefits from the advantages of using curved surfaces without adding complexity to the rasterization stage but requires a suitable interface to process the surface patch data to form polygon based data. Two methods are commonly employed in the tessellation process for converting the curved surface to a series of polygons: either forward differencing or recursive subdivision. The present invention is derived from the recursive subdivision method.
In the parametric modelling stage of a combined 3-D graphics system (i.e. one that combines a tessellation stage to produce polygons for the latter rendering stage), a plurality of curved surfaces patches are fitted to the surface of the object to define areas of the object. A number of different standards for defining the behaviour of such patches with respect to their defining control points are known. One such standard is Bezier patches, for example see “Advanced Animation and Rendering Techniques” pp 66–68 by Watt & Watt or “Computer Graphics Principles and Practice” pp 471–530 by Foley Van Dam et al. Methods of transforming the control points corresponding to one format of patch to new positions corresponding to a different patch type so that the final surfaces are identical are also known. These patches are often of bicubic order.
Of the common parametric patches, there are two main variations. The first is the family of ‘standard’ mpm-rational surface patches, while the second is the super-set of rational patches. Rational patches have certain modelling advantages over the simpler non-rational variety but can be slightly more complex to process in some respects. Both types of patches are well described in the previous two references, however to simplify description of the embodiment, the following summary is presented. For a non-rational parametric surface, the 3D position can be described as:
                    B        _                    non        -        rational              ⁡          (              s        ,        t            )        =      (                                        x            ⁡                          (                              s                ,                t                            )                                                                        y            ⁡                          (                              s                ,                t                            )                                                                        z            ⁡                          (                              s                ,                t                            )                                            )  where each of x(s,t), y(s,t), and z(s,t) are scalar parametric polynomials of the same degree, and 0≦s,t≦1. In the case of a bicubic (i.e. the product of two cubics) Bezier surface the polynomial is of degree 6. The Bezier equations and the respective x, y, and z components of the surface's control points define the shape of the surface.
A non-rational surface extends the definition by introducing a fourth polynomial w(s,t) with a corresponding additional positive “w” value in each of the control points. The surface position is then defined by:
                    B        _            rational        ⁡          (              s        ,        t            )        =            1              w        ⁡                  (                      s            ,            t                    )                      ⁢          (                                                  x              ⁡                              (                                  s                  ,                  t                                )                                                                                        y              ⁡                              (                                  s                  ,                  t                                )                                                                                        z              ⁡                              (                                  s                  ,                  t                                )                                                        )      It is also well known in the art (see previous references) that the popular types of parametric surfaces patches can be conveniently expressed in matrix form. For example, a bicubic Bezier patch, Bbez(s,t) can be expressed as:
                    B        _            bez        ⁡          (              s        ,        t            )        =            [                        s          3                ⁢                  s          2                ⁢        s1            ]        ⁢                  QPQ        T            ⁡              [                                                            t                3                                                                                        t                2                                                                        t                                                          1                                      ]                            where Q is a matrix of scalar constants and P is the matrix of control points for the surface        
  Q  =                    [                                                            -                1                                                    3                                                      -                3                                                    1                                                          3                                                      -                6                                                    3                                      0                                                                          -                3                                                    3                                      0                                      0                                                          1                                      0                                      0                                      0                                      ]            ⁢      P        =          [                                                                  P                _                            00                                                                          P                _                            01                                                                          P                _                            02                                                                          P                _                            03                                                                                          P                _                            10                                                                          P                _                            11                                                                          P                _                            12                                                                          P                _                            03                                                                                          P                _                            20                                                                          P                _                            21                                                                          P                _                            22                                                                          P                _                            03                                                                                          P                _                            30                                                                          P                _                            31                                                                          P                _                            32                                                                          P                _                            03                                          ]      
Note that P is numbered as PST.
Conversion of the patches to tessellating triangles via the recursive subdivision method is achieved by initially dividing each patch into two sub-patches across either one of its two parameter dimensions (i.e. s or t). This is shown in FIGS. 1a and 1b, in which the patch, with control points, has been portrayed in its parameter space. Each of the sub-patches can then be further sub-divided until the correct level of sub-division is achieved. Once this has been achieved, the resulting sub-patches are each treated as non-planar quadrilaterals, and a set pattern of triangles is superimposed onto the sub-patches, the vertices of the triangles calculated, and the triangles output.
FIG. 2 is a schematic showing conceptual processing of a patch by subdivision with three levels of subdivision applied. From FIG. 2, it can be seen that the processing takes the form of a binary tree progressing from the original, or “root”, patch, through intermediate levels of patches to end-point patches termed “leaf” patches. Each leaf patch is used to generate the vertices defining the tessellating triangles required for the rasterization stage of rendering.
In the known system of recursive sub-division, tessellation is traditionally implemented on a CPU as a large number of calculations are required for each stage. Examining the series of calculations involved shows that, when using a CPU, it is efficient to store the intermediate results on a stack, as the same intermediate result is used on a number of the paths to the leaf patches. Use of the stack therefore minimises the number of calculations performed. We have appreciated that for a hardware implementation this is not practical for two reasons: internal (i.e. on-chip) storage is expensive and the retrieval of large amounts of externally stored data can cause a bottleneck in the performance of the system.
The present invention in a first aspect aims to ameliorate these problems. It provides an interface for converting parametric modelled data to polygon based data using recursive sub-division in a way which provides high computational performance whilst minimising memory and memory bandwidth usage.
According to the invention in a first aspect, there is provided an interface according to claim 12. Preferred features of the first aspect of the invention are defined in dependent claims 13 to 16.
There is also provided a method of interfacing between a parametric modelling unit and a polygon based rendering system according to claim 16. Preferred method steps are defined in dependent claims 17 to 19.
A second problem which occurs when interfacing between parametric data and polygon based data in a combined graphics system is that different levels of subdivision may be required to convert parametric data relating to a first patch and parametric data relating to a second patch, where the first and second patches represent adjacent areas of the object being modelled. Patches which define highly curved surfaces must be more highly subdivided than patches which represent a flatter surface when converting the parametric data to polygon based data if the benefits of parametric modelling are not to be lost. If conversion of adjacent patches is not constrained to apply the same level of subdivision to each patch, then cracks can appear in the modelled object because the surface with the higher level of subdivision has extra sample points and thus potentially a slightly different shape. The problem of cracking is illustrated in FIG. 4.
One solution to the problem of cracking is to use the same level of subdivision on all patches. However, this results in some patches being excessively subdivided when they could be tessellated adequately at a less divided level and does not target the processing to the areas where it is necessary to produce adequate results.
Another solution is to process each patch to a level of subdivision sufficient to represent the surface adequately, and to then insert a so-called “stitching mesh” between adjacent surface patches which have different subdivision levels. The stitching mesh thus covers any potential cracks as shown in FIG. 5a. In the diagram, two adjacent patches are subdivided to different levels—one uses 2×4 sub-patches while the other is represented by no subdivisions, i.e. a single quadrilateral. The ‘abutting’ contour on the 2×4 patch consists of vertices, A, B, C, D, & E, while the equivalent for the 1×1 subdivision consists of the edge AE. To prevent a gap in the surface from appearing, the additional triangles, ABC, ACE and CDE are created.
Unfortunately, such connecting meshes may introduce abrupt changes in surface direction. We have also appreciated that stitching the edges of adjacent patches together is computationally intensive and requires the stitching mesh to be regenerated as the subdivision level changes.
Clark [“A Fast Scan Line Algorithm for Rendering Parametric Surfaces”. Computer Graphics 13(2), 289–99] proposed an alternative technique which even permits different levels of subdivision within each patch. As part of this method, the cracking problem, had to be ‘solved’. Clark's solution is to deliberately ‘flatten’ the edges of higher subdivision regions where they meet lower subdivision regions. This is shown in FIG. 5b. The ‘shared’ boundary between the high-subdivision region and the lowe-subdivision area has been ‘flattened’ on the high subdivision region so that it mathematically matches the boundary of the low-subdivision region. Comparing this to the approach in FIG. 5a, it can be seen that the vertices, B, C, & D now lie on the line AE.
Although this scheme is mathematically correct, it has a subtle flaw. Computer graphics hardware has limited precision and is unable to represent exact polygon vertex locations. It is therefore frequently impossible to exactly place a flattened vertex on the shared boundary. This leads to problems caused by “T-Joints”, as well known in the art. This is illustrated in FIG. 5c, wherein an inaccuracy causes a very small gap to appear. Although this gap is typically tiny, it can still be visible in the rendered images as sets of semi-random pixel holes lying along the edges of the otherwise abutting triangles. As the image is animated, these will ‘twinkle’ on and off and are easily seen.
We have appreciated that these T-Joints could be fixed by again introducing stitching polygons, however this is a rather inefficient approach since such polygons are tiny and the ‘set-up’ costs involved in polygon rendering would be better utilised on more significantly sized polygons.
Yet another approach, as used by Pixar's Renderman system, is to subdivide the patches until the resulting polygons are smaller than a pixel. These micro-polygons can then be treated as ‘points’. This methord generates vast amounts of data and is not really suitable for real-time rendering.
The options for crack-free subdivision in the current art can thus be summarised as follows:    1) Subdivide all patches of the model to the same subdivision level. This is simple but wasteful of resources.    2) Within each patch subdivide uniformly, and then use stitching polygons to hide gabs between patches divided non-uniformly. It is not ideal as the stitching polygons are additional costs and can induce abrupt changes in direction (as seen in FIG. 5a).    3) Use Clark's method, allowing non-uniform subdivision even within patches, but suffer from T-Joint problems.    4) Apply further stitching polygons to Clark's method.    5) Subdivide the mesh into micro-polygons.
We have appreciated that allowing non-uniform subdivision along patch edges is desirable since it allows the joining of different patches without cracking at the joints. It is also desirable to allow non-uniform subdivision within patches, as is possible with Clark's method, as this can allow a more efficient use of polygons as a gradual transition from a high subdivision edge on one side of a patch to a low subdivision edge on the opposite would require fewer polygons than in a system where the patch is internally subdivided uniformly. We have also appreciated that a system which does not need stitching polygons, either internally or on the boundaries, and also does not introduce T-Joints is highly desirable.
The present invention in a second aspect therefore supports “irregular patch” processing, that is processing of patch data to different subdivision levels in different subdivision directions within the patch but avoiding the problems with Clark's scheme. By forming different numbers of vertices on different edges of the “irregular” patch, we have eliminated the need for stitching meshes to prevent cracking between the tessellated patches that are modelling adjacent areas of objects. Supporting irregular tessellation allows adjacent edges of adjoining patches to have the same number of polygon vertices without affecting the level of subdivision of the patch for the remaining edges. An example, showing the boundary of two unequally subdivided patches, is given in FIG. 13b. 
According to the present invention in a second aspect, there is provided an interface according to claim 8. Preferred features of the second aspect of the invention are detailed in dependent claim 9. There is also provided a method of interfacing between a parametric modelling unit and a polygon based rendering system according to claim 10.
Irregular levels of sub-division are supported by automatically generating a mesh from the final sub-patch that has a suitable number of vertices along each edge of the quadrilateral. This allows simple joining of polygonised patches without cracks appearing.
A further problem with known interfacing techniques is so-called polygon popping. For the interfacing of different patches it has been assumed that each edge of every patch has its own subdivision control value. To allow the smooth animation of objects as the lever of subdivision changes, these values are assumed to take floating point or at least contain fractional parts. Polygon popping is a term used to describe the sudden movements in the points of the tessellated polygons that can occur when a small fractional change in the subdivision control value causes an extra step of processing (i.e. an extra binary subdivision of the patch) to be performed. Although the edge subdivision control value may take any value, the preferred tessellation technique is constrained to perform binary patch subdivision to the next nearest power of 2. Thus increasing the subdivision ratio even a small amount may cause the actual level of subdivision to increase dramatically. For example if the subdivision value specified for each edge is 4, then subdivision results in 16 leaf patches. If the subdivision value for each edge is increased from 4 to 4.1, the next larger power of 2 is 8 and the resulting subdivision gives rise to 64 leaf patches. Thus many new triangles have appeared in the object. Unless this process is well controlled it causes undesirable visual effects in the animation as shown in FIG. 3.
In FIG. 3a, the curved surface has been subdivided into two quadrilateral regions. The ‘front-most’ curved edge of the patch is thus approximated by the line segments AB and BC. In FIG. 3b, the level of subdivision is increased (in one dimension only) so that along the front edge, two new points, D & E, have been generated. The front edge of the patch is then represented by the line segments AD, DB, BE and EC. The change in shape from ABC to ADBEC is relatively large, and the new points D & E can be said to have jumped or “popped” into view. This is most readily seen in this example with point E which will have appeared to have jumped from the position E′.
The present invention, in a third aspect, aims to ameliorate the visual problems associated with polygon popping.
According to the present invention in a third aspect there is provided an interface according to claim 1.
Preferred features of the third aspect of the invention are defined in dependent claims 2 and 3. There is also provided a method of interfacing between a parametric modelling unit and a polygon based rendering system according to claim 4. Preferred method steps are defined in dependent claims 5 to 7.
The present invention in a third aspect produces a smoother looking animated image when changing levels of detail of a model using high order surfaces. Preferably it uses a weighted blend between the linear and cubic subdivision of the final tessellated leaf-patch. The weighting factor for this blend is preferably determined by the ratio between the required subdivision value and next smaller power of 2.
When lighting and shading operations are applied to surfaces in 3-D graphics, there is usually a requirement that the surface normal at a point, i.e. a vector perpendicular to the surface at that location, be known. For the purposes of shading a tessellated surface, surface normals need only be computed at the computed triangle verticles.
As descrived by Watt and Watt, Forley et al, and Farin, [“Curves and Surfaces for CAGD. A Practical Guide”. 4th Edition, Academic Press, ISBN 0-12-249054-1, pp 244–247], the standard way to obtain the normal at a point is to calculate two (linearly independent) tangent vectors at that point and take their cross product. If desired, the result can later be converted into a unit computing the first partial derivatives of the surface with respect to the s and t parameters.
Without loss of generality, if we restrict the surface normal calculations to only be done at the corner points of patches, then non-rational Bezier surfaces have the very convenient property that the differences between a corner control point and each of its two nearest edge control points are scalar multiples of the respective first partial derivatives. This is shown in FIG. 19 wherein ‘Tangent S’ coincides with the difference of corner point P00 and its neighbour control point P10, while ‘Tangent T’ coincides with the difference between the corner and control point P01.
A number of systems use this fact (in addition to repeated subdivision) to compute the normals at various locations on the patch.
Unfortunately, this calculation can frequently fail. The requirement is that the tangent vectors are linearly independent and control points of the Bezier patch, especially those neighbouring the corner points, can sometimes be coincident. This means that one or both of the first partial derivates may be zero, resulting in an incorrect normal. Such surfaces patches are often referred to as ‘degenerate’, and some systems may consider them to be ‘illegal’. This is rather unfortunate as such surface arrangements of control points are often needed to model completely valid shapes and can easily be generated by modelling software packages.
One known and rather pragmatic solution is that of evaluating the surface at two points slightly offset from the corner in the s and t parameters. The two tangent vectors are then approximated by taking the differences between these computed points and the patch corner. This will usually provide an adequate result, but is costly in terms of additional calculation.
By referring back to the definition of a tangent vector and applying calculus, one can see that the 2nd partial derivative can be employed if the first is zero. Watt and Watt [“Advanced Animation and Rendering Techniques. Theory and Practice”. ACM Press. ISBN 0-201-54412-1] demonstrate, again for non-rational Beziers patches, that in this situation the difference between the corner control point and the subsequent multiple of the 2nd partial derivative. Again referring to FIG. 19, if P01 and P00 were coincident, for example, then the difference of P02 and P00 would yield a potential tangent. If this were also zero, a similar process can be employed for the 3rd partial derivative by taking the difference with P03.
Unfortunately, even this approach can fail. All the points along an edge of patch may be coincident, as may occur when a patch is modelling an octant of a sphere and the patch has become ‘triangular’. In this particular situation a 2nd partial derivative may be chosen. Farin also describes an even subtler problem: although non-zero partial derivatives in s and t might exist, in some situations they can be parallel. The cross product will then give a zero, and hence invalid, normal. Farin describes the solution for one particular case.
In a fourth aspect, the invention will present a method of computing the surface normal which is not only robust but also efficiently computes the normals for Rational Bezier surfaces.